/**
*	Name: pseudo.c
*	Author: David Palma, 12054
*	Description: Gerador de numeros Pseudo-Aleatórios
*	Módulo em C importado pela biblioteca ctypes de Python
*
*	Beja, 8 de Fevereiro de 2012
*
*	Estatisticas(segundos):
*	Maquina Virtual VMWare Player: Mint 12 Gnome 32 bits
*	Intel C2D 8600@2.4Ghz
*
*	1000: 0.000000 (inferior a precisao)
*	10 000: 0.000000 (inferior a precisao)
*	100 000: 0.010000
*	1 000 000 000: 0.050000
*	10 000 000 000: 0.530000
*	100 000 000 000: 5.300000
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*
*	Calcula 'k' numeros aleatorios utilizando o algoritmo descrito no enunciado
*/
void pseudo_rand(int k){

	double t1, t2; /* Valores de clocks ao inicio e ao fim do programa */

	/* Tempo do inicio da execucao do programa */
	t1 = clock();
	
	/* Declaracao de variaveis */	
	unsigned int i, j, r, l, p, N;
	unsigned int T[1000]; /* Tabela de 1000 entradas */
	unsigned int count[10]; /* Tabela com as frequencias dos digitos */
	unsigned int z[4]; /* Tabela com o valor z */

	/* Inicializacao da tabela count */
	for(j = 0; j < 10; j++){
		count[j] = 0;
	}

	/* 1. Inicializacao da tabela com 1000 entradas */
	for(j = 0; j < 1000; j++){
		do{
			r = rand() % 10; /* Valor pseudoaleatorio entre 0 a 10 */
		}
		while(count[r] > 99);
		T[j] = r; /* Coloca o valor aleatorio na posicao actual de T */
		count[r]++;
	}

	/* Inicializacao da seed da funcao de numeros aleatorios rand() */
	srand((unsigned)time(NULL));

	/* Ciclo geral com 'k' iteracoes de numeros aleatorios */
	for(i = 0; i < k; i++){

		/* 2. Inicializacao do valor p com valor entre 0 e 999 */
		p = rand() % 1000;

		/* 3. Gerar Numero aleatorio Nk */
		for(j = 0; j < 4; j++){
			if(p < 1000-j){
				l = p+j;
			}
			else {
				l = 0;
			}
			z[j] = T[l];
			T[l] = T[0];
			T[0] = z[j];
		}
		
		/* Formacao de Nk a partir de z utilizando Shift binario */
		N = z[0] << 12 | z[1] << 8 | z[2] << 4 | z[3];
		
		/* Formacao do valor p a ser utilizado nas proximas iteracoes */
		p = z[0]*100 + z[1]*10 + z[2];
	}
	
	/* Tempo do fim da execucao do programa */
	t2 = clock();
 	printf("Tempo de execucao total: %f\n", ((t2 - t1) / CLOCKS_PER_SEC));
	return;
}

